#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        queue<int> save;
        k %= n;

        int i = n - 1;
        int tmp = k;
        for (; i >= 0; i--)
        {
            if (tmp-- > 0) save.push(nums[i]);
            int copy = i - k;
            if (copy >= 0) nums[i] = nums[copy];
            else
            {
                nums[i] = save.front();
                save.pop();
            }
        }
    }
};